package com.ljy.my_study.lintcode.获取子字符串在字符串中索引;

/**
 * @author James
 * @date 2018年9月21日
 */
public class SubStringMain2 {
	public static void main(String[] args) {
		SubStringMain2 testMain=new SubStringMain2();
		System.out.println(testMain.strStr("abcde","e"));
	}
	
	public int strStr(String ts, String ps) {
		if(ts==null||ps==null) return -1;
		int sourceLen=ts.length();
		int targetLen=ps.length();
		if(sourceLen<targetLen) return -1;
		if(targetLen==0) return 0;
		
		char[] t = ts.toCharArray();

		char[] p = ps.toCharArray();

		int i = 0; // 主串的位置

		int j = 0; // 模式串的位置

		int[] next = getNext(ps);

		while (i < t.length && j < p.length) {

			if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0

				i++;

				j++;

			} else {

				// i不需要回溯了

				// i = i - j + 1;

				j = next[j]; // j回到指定位置

			}

		}

		if (j == p.length) {

			return i - j;

		} else {

			return -1;

		}
	}

	public static int[] getNext(String ps) {

		char[] p = ps.toCharArray();

		int[] next = new int[p.length];

		next[0] = -1;

		int j = 0;

		int k = -1;

		while (j < p.length - 1) {

			if (k == -1 || p[j] == p[k]) {

				next[++j] = ++k;

			} else {

				k = next[k];

			}

		}

		return next;

	}
}
